/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-squares
   @Language: C++
   @Datetime: 19-05-07 09:53
   */


class Solution {
	bool judge(vector<string> &vs){
		for(int row=0; row<vs.size(); ++row)
			for(int i=0; i<vs[row].length() && i<vs.size() && row<vs[i].length(); ++i)
				if(vs[row][i]!=vs[i][row]) return false;
		return true;
	}
	void dfs(vector<vector<string> > &res, vector<string> &vs,
			unordered_map<string,vector<string> > &prefixs){
		if(vs.size()==vs[0].length()) {
			res.push_back(vs);
			return;
		}
		string prefix;
		for(int i=0; i<vs.size(); ++i)
			prefix.push_back(vs[i][vs.size()]);
		for(const auto &word:prefixs[prefix]){
			vs.push_back(word);
			if(judge(vs)) dfs(res,vs,prefixs);
			if(vs.size()) vs.pop_back();
		}
	}
public:
	/*
	 * @param words: a set of words without duplicates count<=1000, length<=5
	 * @return: all word squares
	 */
	vector<vector<string> > wordSquares(vector<string> &words) {
		// write your code here
		unordered_map<string,vector<string> > prefixs;
		for(const auto &word:words)
			for(int len=1; len<word.length(); ++len)
				prefixs[word.substr(0,len)].push_back(word);
		vector<vector<string> > res;
		vector<string> vs;
		for(const auto &word:words){
			vs.push_back(word);
			dfs(res,vs,prefixs);
			if(vs.size()) vs.pop_back();
		}
		return res;
	}
};
